/*
//##############################################################################
// AUTORES: Cesar Luis           Carné: 12539
// SECCIÓN: 40
// FECHA: 05/11/2013
// NOMBRE DEL ARCHIVO: Grafo.java
// DESCRIPCIÓN: Clase para los nodos del grafo.
//##############################################################################
 */
package principal;

// Librerías utilizadas
import java.util.Iterator;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

public class Grafo <T> implements iGrafo <T> {

    private int numNodes;
    private int maxNodes = 100;
    private String[] Vertex;
    private int[][] MA;
    
    //Método constructor
    public Grafo() {        
        numNodes = 0;
        Vertex = new String[maxNodes];
        MA = new int[maxNodes][maxNodes];
    }

    public boolean isEmpity() {
        return (numNodes == 0);
    }
    
    // Método para la inserción de una nueva relación en el grafo

    @Override
    public boolean addRelation(String v1, String v2, int weight) {        
        if (existVertex(v1) != -1 && existVertex(v2) != -1){
            MA[existVertex(v1)][existVertex(v2)] = weight;
            return true;
        }
        return false;
    }    
   
    // Método que inserta un nuevo nodo en el grafo

    @Override
    public boolean addVertex(T value) {
        if (numNodes < maxNodes){
            Vertex[numNodes] = (String)value;            
            numNodes++;
            return true;
        }
        return false;
    }

    // Método que elimina un nodo del grafo
    
    @Override
    public boolean deleteVertex(T value) {
        int j  = existVertex((String)value);
        if (j != -1){
            // Reorganización de la matriz de adyacencia y la lista de vértices
            for (int i = j; i < (numNodes - 1); i++){
                Vertex[i] = Vertex[i+1];
                MA[j][i] = MA[j][i+1];
                MA[i][j] = MA[i+1][j];
            }
            numNodes--;
            return true;
        }        
        return false;
    }
    
    
    // Método que verifica si existe un vértice en el grafo
    public int existVertex(String v){
        for (int i=0; i < Vertex.length; i++){            
            if (Vertex[i].equals(v))
                return i;
        }
        return -1;
    }
    
    // Método para obtener el grafo en forma de String
    public String getGrafo(){
        String Grafo = "";
        for (int i = 0; i < numNodes; i++) {
            for (int j = 0; j < numNodes; j++) {
                Grafo += String.valueOf(MA[j][i]) + "\t";
            }
            Grafo += "\n";
        }
        return Grafo;
    }
    

    /*---------------------- ALGORITMO DE FLOYD ----------------------*/
    /* Recibe la matriz de adyacencia */
    public String floyd() {
        
        // Creamos la matriz con los nodos existentes, tal como lo requiere el método de Floyd.
        int[][] adyacencia = new int[numNodes][numNodes];
        for (int i = 0; i < numNodes; i++) {
            for (int j = 0; j < numNodes; j++) {
                adyacencia[j][i] = MA[j][i];
            }
        }
        
        // Inicio del algoritmo
        int n = adyacencia.length;
        int D[][] = adyacencia;

        String enlaces[][] = new String [n][n];
        String[][] aux_enlaces = new String[adyacencia.length][adyacencia.length];

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                 enlaces[i][j] = "";
                 aux_enlaces[i][j] = "";
           }
        }
        String enl_rec = "";
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    float aux = D[i][j];
                    float aux2 = D[i][k];
                    float aux3 = D[k][j];
                    float aux4 = aux2+aux3;
                    float res = Math.min(aux,aux4);
                    if(aux != aux4) {
                        if(res == aux4) {
                            enl_rec = "";
                            aux_enlaces[i][j] = k + "";
                            enlaces[i][j] = enlaces(i,k,aux_enlaces,enl_rec) + (k+1);
                        }
                     }
                    D[i][j]=(int) res;
                }
             }
        }

        String cadena = "";
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) 
                cadena += D[i][j] + " ";
            cadena += "\n";
        }

        String enlacesres = "";
        for (int i = 0; i <n; i++) {
            for (int j = 0; j < n; j++) {
                if(i != j) {
                    if(enlaces[i][j].equals("") == true)
                        enlacesres += " De ( " + (i+1) + " a " + (j+1) + " ) = " + "( " + (i+1) + " , " + (j+1) + " )" + "\n";
                    else
                        enlacesres += " De ( " + (i+1) + " a " + (j+1) + " ) = ( " + (i+1) + " , " + enlaces[i][j] + " , " + (j+1) + ")\n";
                }
            }
        }
        
        return "Las distancias minimas entre nodos son: \n" + cadena + "\nLos caminos minimos entre nodos son:\n" + enlacesres;
    }
 
    public String enlaces(int i, int k, String[][] aux_enlaces, String enl_rec) {
        if(aux_enlaces[i][k].equals("") == true)
            return "";
        else {
            enl_rec += enlaces(i,Integer.parseInt(aux_enlaces[i][k].toString()),aux_enlaces,enl_rec) + (Integer.parseInt(aux_enlaces[i][k].toString())+1) + " , ";
            return enl_rec;
        }
    } 


    @Override
    public boolean setWeight(String v1, String v2, int weight) {
        if (existVertex(v1) != -1 && existVertex(v2) != -1){
            MA[existVertex(v1)][existVertex(v2)] = weight;
            return true;
        }
        return false;
    }
    
}
